home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / smaltalk / manchest.lha / MANCHESTER / manchester / 2.2 / BinaryTree.st < prev    next >
Text File  |  1993-07-24  |  3KB  |  122 lines
  1. "    NAME        BinaryTree
  2.     AUTHOR        TPH@cs.man.ac.uk
  3.     FUNCTION benchmark program --- builds and walks a tree 
  4.     ST-VERSIONS    2.2
  5.     PREREQUISITES     
  6.     CONFLICTS    
  7.     DISTRIBUTION      world
  8.     VERSION        1.1
  9.     DATE    22 Jan 1989
  10. SUMMARY    BinaryTree
  11.     is a benchmark program which builds and walks a tree,
  12.    based on an example in Hope provided by Ian Watson.(2.2). TPH
  13. "!
  14. 'From Smalltalk-80, Version 2.2 of July 4, 1987 on 15 February 1988 at 6:48:12 pm'!
  15.  
  16. Object subclass: #BinaryTreeLeaf
  17.     instanceVariableNames: 'contents '
  18.     classVariableNames: ''
  19.     poolDictionaries: ''
  20.     category: 'Parallel-algorithms'!
  21.  
  22.  
  23. !BinaryTreeLeaf methodsFor: 'accessing'!
  24.  
  25. sum
  26.     "The receiver is a leaf, so answer with the contents."
  27.  
  28.     ^contents! !
  29.  
  30. !BinaryTreeLeaf methodsFor: 'private'!
  31.  
  32. setContents: anObject
  33.     "Set the contents to anObject."
  34.  
  35.     contents _ anObject! !
  36. "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!
  37.  
  38. BinaryTreeLeaf class
  39.     instanceVariableNames: ''!
  40.  
  41.  
  42. !BinaryTreeLeaf class methodsFor: 'instance creation'!
  43.  
  44. with: anObject
  45.     "Create a new instance of the receiver, containing anObject."
  46.  
  47.     ^self new setContents: anObject! !
  48.  
  49. 'From Smalltalk-80, Version 2.2 of July 4, 1987 on 15 February 1988 at 6:47:53 pm'!
  50.  
  51. Object subclass: #BinaryTreeNode
  52.     instanceVariableNames: 'left right '
  53.     classVariableNames: ''
  54.     poolDictionaries: ''
  55.     category: 'Parallel-algorithms'!
  56.  
  57.  
  58. !BinaryTreeNode methodsFor: 'accessing'!
  59.  
  60. sum
  61.     "Walk the tree represented by the receiver, and sum the nodes."
  62.  
  63.     ^(1 + (left sum + right sum // 2))! !
  64.  
  65. !BinaryTreeNode methodsFor: 'private'!
  66.  
  67. setLeft: leftNode setRight: rightNode
  68.     "Set the left and right nodes appropriately."
  69.  
  70.     left _ leftNode.
  71.     right _ rightNode! !
  72. "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!
  73.  
  74. BinaryTreeNode class
  75.     instanceVariableNames: ''!
  76.  
  77.  
  78. !BinaryTreeNode class methodsFor: 'instance creation'!
  79.  
  80. grow: aNumber
  81.     "Answer with a tree of size aNumber."
  82.  
  83.     (aNumber = 0)
  84.         ifTrue: [^BinaryTreeLeaf with: aNumber]
  85.         ifFalse: [^self
  86.                     left: (self grow: aNumber - 1)
  87.                     right: (self grow: aNumber - 1)]!
  88.  
  89. left: leftNode right: rightNode
  90.     "Create a new instance of the receiver, with references
  91.      to leftNode and rightNode."
  92.  
  93.     ^self new setLeft: leftNode setRight: rightNode! !
  94.  
  95. !BinaryTreeNode class methodsFor: 'examples'!
  96.  
  97. benchmarkDepth: depth repeated: count
  98.     "BinaryTreeNode benchmarkDepth: 8 repeated: 10."
  99.  
  100.     Transcript
  101.         cr;
  102.         show: depth printString;
  103.         tab;
  104.         show: ((Time millisecondsToRun: [
  105.             count timesRepeat: [
  106.                 (BinaryTreeNode grow: depth) sum]]) / count asFloat) printString!
  107.  
  108. exampleWorkspace
  109.     "Select and execute the expressions below to run the benchmarks."
  110.  
  111.     "Smalltalk growOTBy: 20000."        "Needed for large trees."
  112.     "Smalltalk oopsLeft."
  113.  
  114.     "
  115.     0 to: 10 do: [:num |
  116.         BinaryTreeNode benchmarkDepth: num repeated: 30].
  117.     11 to: 12 do: [:num |
  118.         BinaryTreeNode benchmarkDepth: num repeated: 10].
  119.     BinaryTreeNode benchmarkDepth: 13 repeated: 5.
  120.     BinaryTreeNode benchmarkDepth: 14 repeated: 1.
  121.     "! !
  122.